package Offer;

import java.util.HashMap;
import java.util.Map;

/*
    题目:
        请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，
        每个节点除了有一个 next 指针指向下一个节点，还有一个 random
        指针指向链表中的任意节点或者 null。
        -------------------------------------------------
        输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
        输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

    思路:
        这里给的head中，第二个值是链表结点的序号从0开始，要求对给
        出的链表进行复制本题的难点在于random域值的确认，因为第一个
        结点的random指向的结点位置是随机的，而此时后面的结点还没有生成(所以常规的方法是行不通的)
        本题是在简单链表复制的进阶版

    这是拷贝普通链表的逻辑 类似插入排序
    public Node copyRandomList(Node head) {
        Node pre = new Node(-1);
        Node dump = pre;
        // pre.next = head;
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);  //复制结点
            pre.next = node;
            cur = cur.next;
            pre = pre.next;
        }
        return dump.next;
    }


* */
public class T35_copyRandomList {

    /**
     * 使用哈希表法
     */
    public Node copyRandomList(Node head) {
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();  //建立新旧链表相同结点的映射关系

        while (cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while (cur != null) {
            // 新结点的next 可以通过旧结点的next去取hash表，得到新结点的next
            map.get(cur).next = map.get(cur.next);
            // 新结点的random 可以通过旧结点的random,然后从hash表拿到新结点
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    /**
     * 合并+拆分
     */
    public Node copyRandomList_2(Node head) {
        Node cur = head;

        if (head == null) {
            return null;
        }

        //合并新旧链表
        while (cur != null) {
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = cur.next.next;
        }

        cur = head;
        //设置新链表的random
        while (cur != null) {
            if (cur.random != null) { //如果cur不为空，那么cur.next也不会为空;当cur.random不为空，那么cur.next.random也不会为空
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        //拆分新旧链表
        cur = head;
        Node p = cur.next, res = p;
        while (p.next != null) {    //因为下面用到了next.next,所以这里用p.next!=null而不是p!=null
            cur.next = cur.next.next;
            p.next = p.next.next;
            cur = cur.next;
            p = p.next;
        }
        cur.next = null;    //这里不设置为null的话，cur的下一个结点就还是新链表的尾结点

        return res;
    }
}


/**
 * 带的是随机指针random和next指针
 */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}